package String;

public class KMP {
    public static int[] getNext(String pattern) {
        int[] next = new int[pattern.length()];
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < pattern.length() - 1) {
            if (k == -1 || pattern.charAt(k) == pattern.charAt(j)) {
                j++;
                k++;
                next[j] = k;
            } else k = next[k];
        }

        return next;
    }

    public static int KMP(String target, String pattern) {
        int i = 0;    //target 的指针
        int j = -1;    //pattern 的指针
        int[] next = getNext(pattern);
        while (i < target.length() && j < pattern.length()) {
            if (j == -1 || target.charAt(i) == pattern.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];
                if (target.length() - i + 1 < pattern.length() - j + 1) break;
            }
        }
        return j == pattern.length() ? i - pattern.length() + 1 : -1;
    }

    public static void main(String[] args) {
        System.out.println(KMP("ababca", "baba"));
    }

}
